﻿using System;
using System.Collections.Generic;

namespace SubsetSumSOfK
{
    class SubsetSumSOfK
    {
        struct Subsets
        {
            public readonly int Sum, ArrayIndex, SubsetIndex;

            public Subsets(int subsetSum, int arrayIndex, int subsetIndex)
            {
                Sum = subsetSum;
                ArrayIndex = arrayIndex;
                SubsetIndex = subsetIndex;
            }
        }

        static void PrintResult(int[] array, List<int> indexs, bool isNotFound)
        {
            if (isNotFound)
            {
                Console.WriteLine("Doesn't exist");
            }
            else
            {
                Console.Write("Yes (");
                for (int index = indexs.Count - 1; index > 0; index--)
                {
                    Console.Write("{0} + ", array[indexs[index]]);
                }
                Console.WriteLine("{0})", array[indexs[0]]);
            }
        }

        static List<int> FoundParentSequenceOfIndexes(List<Subsets> subsetSums)
        {
            List<int> indexes = new List<int>();
            Subsets currentSubsetSum = subsetSums[subsetSums.Count - 1];
            indexes.Add(currentSubsetSum.ArrayIndex);
            int currentIndex = currentSubsetSum.SubsetIndex;
            while (currentIndex != -1)
            {
                currentSubsetSum = subsetSums[currentIndex];
                indexes.Add(currentSubsetSum.ArrayIndex);
                currentIndex = currentSubsetSum.SubsetIndex;
            }

            return indexes;
        }

        static void FoundSubsetSum(int[] array, int sum, int numberOfElements)
        {
            List<Subsets> subsetSums = new List<Subsets>(1 << array.Length);
            subsetSums.Add(new Subsets(array[0], 0, -1));

            if (numberOfElements == 1)
            {
                for (int index = 0, length = array.Length; index < length; index++)
                {
                    if (array[index] == sum)
                    {
                        PrintResult(array, new List<int>(new int[]{ index }), false);
                        return;
                    }
                }
            }

            for (int index = 1, length = array.Length; index < length; index++) //Each element
            {
                for (int sumsIndex = 0, count = subsetSums.Count; sumsIndex < count; sumsIndex++) //Each parent subset sum
                {
                    int currentSum = array[index] + subsetSums[sumsIndex].Sum;
                    subsetSums.Add(new Subsets(currentSum, index, sumsIndex));
                    if (currentSum == sum)
                    {
                        List<int> subsetIndexes = FoundParentSequenceOfIndexes(subsetSums);
                        if (subsetIndexes.Count == numberOfElements)
                        {
                            PrintResult(array, subsetIndexes, false);
                            return;
                        }
                    }
                }
                subsetSums.Add(new Subsets(array[index], index, -1));
            }
            //If nothing is found
            PrintResult(array, new List<int>(), true);
        }

        static void Main()
        {
            Console.Write("Please enter the length of your array: ");
            int arrayLength = int.Parse(Console.ReadLine());

            Console.Write("Enter an integer for S: ");
            int s = int.Parse(Console.ReadLine());

            Console.Write("Enter and integer for K: ");
            int k = int.Parse(Console.ReadLine());

            int[] numbers = new int[arrayLength];
            for (int index = 0; index < arrayLength; index++)
            {
                Console.Write("Index [{0}]: ", index);
                numbers[index] = int.Parse(Console.ReadLine());
            }

            FoundSubsetSum(numbers, s, k);
        }
    }
}
